Strukturelle Analysen im unteren Komplexitätsbereich

Projektleitung und Mitarbeiter

Mittelgeber :

Forschungsbericht : 1994-1996

Tel./ Fax.:

Projektbeschreibung

Das Hauptaugenmerk in diesem Arbeitsabschnitt lag vor allem in der Übertragung von bekannten Techniken und Ergebnissen auf uniforme und nichtuniforme Klassen im unteren Komplexitätsbereich, d. h. auf dem Bereich logarithmisch platzbeschränkter Klassen und darunter. Bei der strukturellen Analyse konnte z. B. das Ergebnis von Immerman and Szelepsényi auf sublogarithmische nichtuniforme Platzkomplexitätsklassen verbessert werden, indem die Technik des induktiven Zählens auf diese Klassen übertragen wurde. Desweiteren gelang es neue Charakterisierungen von Komplexitätsklassen durch eingeschränkte Orakelzugriffe anzugeben. Diese Darstellungen fügen sich nahtlos in die bekannten Darstellungen ein und haben ein erstaunlich großes Anwendungsfeld z. B. für Aufwärts-Separationen, Tiefe-Uniformitäts Trade-offs und Untersuchungen über Inklusionsvollständigkeit für unäre Sprachen.

Publikationen

INDEX HOME SUCHEN KONTAKT LINKS